package com.cat.dataStructure;

import java.util.HashSet;
import java.util.Set;

/**
 * @author 曲大人的喵
 * @description https://leetcode.cn/problems/k-divisible-elements-subarrays/description/
 * @create 2025/9/27 19:51
 * @since JDK17
 */

public class Solution86 {
    public int countDistinct(int[] nums, int k, int p) {
        int n = nums.length, ans = 0;
        long[] pow = new long[n];
        long base = 499, h = 0;
        Set<Long> set = new HashSet<>();
        pow[0] = 1;
        for (int i = 1; i < n; i++) {
            pow[i] = pow[i - 1] * base;
        }
        for (int len = 1; len <= n; len++) {
            h = 0;
            for (int l = 0, r = 0, cnt = 0; r < n; r++) {
                h = h * base + nums[r]; // 收集哈希值
                cnt += nums[r] % p == 0 ? 1 : 0;    //
                if (r - l + 1 < len) {
                    continue;
                }
                if (cnt <= k && !set.contains(h)) {
                    ans++;
                    set.add(h);
                }
                cnt -= nums[l] % p == 0 ? 1 : 0;
                h -= nums[l++] * pow[len - 1];
            }
        }

        return ans;
    }
}
